Section: New Results

Algebraic algorithms for geometric computing

On the isotopic meshing of an algebraic implicit surface

Participant : Bernard Mourrain.

In [22] , we present a new and complete algorithm for computing the topology of an algebraic surface given by a squarefree polynomial in $\mathbb{Q}[X,Y,Z]$. Our algorithm involves only subresultant computations and entirely relies on rational manipulation, which makes it direct to implement. We extend the work in [15], on the topology of non-reduced algebraic space curves, and apply it to the polar curve or apparent contour of the surface S. We exploit simple algebraic criterion to certify the pseudo-genericity and genericity position of the surface. This gives us rational parametrizations of the components of the polar curve, which are used to lift the topology of the projection of the polar curve. We deduce the connection of the two-dimensional components above the cell defined by the projection of the polar curve. A complexity analysis of the algorithm is provided leading to a bound in ${\widetilde{𝒪}}_B\left(d^{15}\tau \right)$ for the complexity of the computation of the topology of an implicit algebraic surface defined by integer coefficients polynomial of degree d and coefficients size τ . Examples illustrate the implementation in Mathemagix of this first complete code for certified topology of algebraic surfaces.

This is a joint work with Daouda Niang Diatta, Olivier Ruatta (XLIM, University of Limoges).

Moment matrices, border basis and real radical computation

Participant : Bernard Mourrain.

In [32] , we describe new methods to compute the radical (resp. real radical) of an ideal, assuming its complex (resp. real) variety is finite. The aim is to combine approaches for solving a system of polynomial equations with dual methods which involve moment matrices and semi-definite programming. While border basis algorithms are efficient and numerically stable for computing complex roots, algorithms based on moment matrices allow the incorporation of additional polynomials, e.g., to restrict the computation to real roots or to eliminate multiple solutions. The proposed algorithm can be used to compute a border basis of the input ideal and, as opposed to other approaches, it can also compute the quotient structure of the (real) radical ideal directly, i.e., without prior algebraic techniques such as Gröbner bases. It thus combines the strengths of existing algorithms and provides a unified treatment for the computation of border bases for the ideal, the radical ideal and the real radical ideal.

This is a joint work with Jean-Bernard Lasserre (LAAS, Toulouse), Monique Laurent (CWI, Amsterdam, Netherland), Philipp Rostalski (University of California, Berkeley, US) Philippe Trébuchet (APR, LIP6, Paris).

On the computation of matrices of traces and radicals of ideals

Participant : Bernard Mourrain.

Let $f_1,...,f_s\in 𝕂[x_1,...,x_m]$ be a system of polynomials generating a zero-dimensional ideal $I$, where $𝕂$ is an arbitrary algebraically closed field. In [31] , we study the computation of “matrices of traces” for the factor algebra $𝒜:=ℂ[x_1,...,x_m]/I$, i.e. matrices with entries which are trace functions of the roots of $I$. Such matrices of traces in turn allow us to compute a system of multiplication matrices $\left\{M_{x_i}\right|i=1,...,m\}$ of the radical $\sqrt{I}$. We first propose a method using Macaulay type resultant matrices of $f_1,...,f_s$ and a polynomial $J$ to compute moment matrices, and in particular matrices of traces for $𝒜$. Here $J$ is a polynomial generalizing the Jacobian. We prove bounds on the degrees needed for the Macaulay matrix in the case when $I$ has finitely many projective roots in ${\mathbb{P}}_{ℂ}^m$. We also extend previous results which work only for the case where $𝒜$ is Gorenstein to the non-Gorenstein case. The second proposed method uses Bezoutian matrices to compute matrices of traces of $𝒜$. Here we need the assumption that $s=m$ and $f_1,...,f_m$ define an affine complete intersection. This second method also works if we have higher dimensional components at infinity. A new explicit description of the generators of $\sqrt{I}$ are given in terms of Bezoutians.

This is a joint work with Itnuit Janovitz-Freireich (Departamento de Matemáticas, Mexico), Lajos Ronayi (Hungarian Academy of Sciences and Budapest University of Technology and Economics, Budapest), Agnes Szanto (Department of Computer Science, North Carolina State University, US).

Border basis representation of a general quotient algebra

Participant : Bernard Mourrain.

In [40] , we generalized the construction of border bases to non-zero dimensional ideals for normal forms compatible with the degree, tackling the remaining obstacle for a general application of border basis methods. First, we give conditions to have a border basis up to a given degree. Next, we describe a new stopping criterion to determine when the reduction with respect to the leading terms is a normal form. This test based on the persistence and regularity theorems of Gotzmann yields a new algorithm for computing a border basis of any ideal, which proceeds incrementally degree by degree until its regularity. We detail it, prove its correctness, present its implementation and report some experimentations which illustrate its practical good behavior.

This is a joint work with Philippe Trébuchet (APR, LIP6, Paris).

Voronoï diagrams of algebraic distance fields

Participant : Bernard Mourrain.

In [25] , we design and implement an efficient and certified algorithm for the computation of Voronoi Diagrams (VD's) constrained to a given domain. Our framework is general and applicable to any VD-type where the distance field is given explicitly or implicitly by a polynomial, notably the anisotropic VD or VD's of non-punctual sites. We use the Bernstein form of polynomials and DeCasteljau's algorithm to subdivide the initial domain and isolate bisector, or domains that contain a Voronoi vertex. The efficiency of our algorithm is due to a filtering process, based on bounding the field over the subdivided domains. This allows us to exclude functions (thus sites) that do not contribute locally to the lower envelope of the lifted diagram. The output is a polygonal description of each Voronoi cell, within any user-defined precision, isotopic to the exact VD. Correctness of the result is implied by the certified approximations of bisector branches, which are computed by existing methods for handling algebraic curves. First experiments with our C++ implementation, based on double precision arithmetic, demonstrate the adaptability of the algorithm.

This is a joint work with Ioannis Emiris (ERGA, National Kapodistrian University of Athens, Greece), Angelos Mantzaflaris (RICAM, Austrian Academy of Sciences, Austria).

Rational invariants of scalings from Hermite normal forms

Participant : Evelyne Hubert.

Scalings form a class of group actions that have both theoretical and practical importance. A scaling is accurately described by an integer matrix. In [39] tools from linear algebra are exploited to compute a minimal generating set of rational invariants, trivial rewriting and rational sections for such a group action. The primary tools used are Hermite normal forms and their unimodular multipliers. With the same line of ideas, a complete solution to the scaling symmetry reduction of a polynomial system is also presented.

This is joint work with George Labahn (University of Waterloo, Canada).

Scaling invariants and symmetry reduction of dynamical systems

Participant : Evelyne Hubert.

The motivation for this subject is to offer an algorithmic scheme for reducing the number of parameters in physical, chemical or biological models. This comes as a special case of a symmetry reduction scheme that can be fully realized by linear algebra over the integers. See http://hal.inria.fr/hal-00668882 . We provide there the algebraic determination of the scaling symmetry of a dynamical system and an complete explicit symmetry reduction scheme with polynomial complexity.

This is joint work with George Labahn (University of Waterloo, Canada).

A computational approach to the discriminant of homogeneous polynomials

Participant : Laurent Busé.

In this work, the discriminant of homogeneous polynomials is studied in two particular cases: a single homogeneous polynomial and a collection of $n-1$ homogeneous polynomials in $n$ variables. In these two cases, the discriminant is defined over a large class of coefficient rings by means of the resultant. Many formal properties and computational rules are provided and the geometric interpretation of the discriminant is investigated over a general coefficient ring, typically a domain.

This work is done in collaboration with Jean-Pierre Jouanolou (University of Strasbourg). A preprint is available at http://hal.inria.fr/hal-00747930/en/ .

Intersection between rational curves and surfaces by means of matrix representations

Participant : Laurent Busé.

In [37] , we propose a survey of matrix representations for parameterized curves and surfaces. Illustrations of the properties of these representations are given for intersection problems. In particular, we focus on the ray/surface intersection which is an important step in ray-tracing algorithms.

A root isolation algorithm for sparse univariate polynomials

Participant : André Galligo.

In [38] , we consider a univariate polynomial $f$ with real coefficients having a high degree $N$ but a rather small number $d+1$ of monomials, with $d\ll N$. Such a sparse polynomial has a number of real roots smaller or equal to $d$. Our target is to find for each real root of $f$ an interval isolating this root from the others. The usual subdivision methods, relying either on Sturm sequences or Moebius transform followed by Descartes’s rule of signs, destruct the sparse structure. Our approach relies on the generalized Budan-Fourier theorem of Coste, Lajous, Lombardi, Roy and the techniques developed in some previous works of Galligo. To such a $f$ is associated a set of $d+1$ $𝔽$-derivatives. The Budan-Fourier function $V_f\left(x\right)$ counts the sign changes in the sequence of $𝔽$-derivatives of $f$ evaluated at $x$. The values at which this function jumps are called the $𝔽$-virtual roots of $f$. These include the real roots of $f$. We also consider the augmented $𝔽$-virtual roots of $f$ and introduce a genericity property which eases our study. We present a real root isolation method and an algorithm which has been implemented in Maple. We rely on an improved generalized Budan-Fourier count applied to both the input polynomial and its reciprocal, together with Newton like approximation steps.

This is a joint work with Maria Emilia Alonso (University of Madrid).

Deformation of roots of polynomials via fractional derivatives

Participant : André Galligo.

In [26] , we first recall the main features of Fractional calculus. In the expression of fractional derivatives of a real polynomial $f\left(x\right)$, we view the order of differentiation $q$ as a new indeterminate; then we define a new bivariate polynomial $Pf(x,q)$. For $0\le q\le 1$, $Pf(x,q)$ defines a homotopy between the polynomials $f\left(x\right)$ and $xf\prime \left(x\right)$. Iterating this construction, we associate to $f\left(x\right)$ a plane spline curve, called the stem of $f$. Stems of classic random polynomials exhibits intriguing patterns; moreover in the complex plane $Pf(x,q)$ creates an unexpected correspondence between the complex roots and the critical points of $f\left(x\right)$. We propose 3 conjectures to describe and explain these phenomena. Illustrations are provided relying on the Computer Algebra System Maple.